#include<stdio.h>
#ifndef FFTCONST_H
#include "fftconst.h"
#endif // FFTCONST_H

int (*cmp)(void *a,void *b)
{
    return (a*a+b*b)-(a*a+b*b);
}
//qsortindex 不是交换值，而是交换索引，因此查排序后的索引直接得到排序结果。
//这有很多好处，特别适合于结构记录排序。ligb20170417
void qsortindex(void * v[],myint *a[],myint *b[],int left,int right,int(*cmp)(void*,void *))
{
    int i,last,j;
    void swap(void *v[],int i,int j);

    if(left>=right)
        return;
    swap(v,left,(left+right)>>1);
    last=left;
    for(i=left+1; i<=right; i++)
        if((j= cmp(a,b,i,left))<0)
            swap(v,++last,i);
    swap(v,left,last);

    qsortindex(a,b,left,last-1);
    qsortindex(a,b,last+1,right);
}

void swap(void *v[], int i,int j)
{
    void * temp;
    temp=v[i];
    v[i]=v[j];
    v[j]=temp;
}

void quicksort(int a[],int left,int right)
{
    int i,j,temp;
    i=left;
    j=right;
    temp=a[left];
    if(left>right)
        return;
    while(i!=j)
    {
        while(a[j]>=temp&&j>i)
            j--;
        if(j>i)
            a[i++]=a[j];
        while(a[i]<=temp&&j>i)
            i++;
        if(j>i)
            a[j--]=a[i];

    }
    a[i]=temp;
    quicksort(a,left,i-1);
    quicksort(a,i+1,right);
}

void Quick_sort(int *a, int len)
{

    int low = 0;

    int high = len - 1;

    int base = a[low];

    if (len > 1)
    {

        while (low < high)
        {

            for (; low < high; high--)
            {

                if (base > a[high])
                {

                    a[low++] = a[high];

                    break;

                }
            }

            for (; low < high; low++)
            {

                if (base < a[low])
                {

                    a[high--] = a[low];

                    break;
                }
            }

        }

        a[low] = base;

        Quick_sort(a, low);

        Quick_sort(a + low + 1, len - 1 - low);

    }
}
